「09」 贪心 3 - 区间问题

区间调度问题

区间调度问题(Interval Scheduling Problem)

数轴上有 $n$ 个开区间 $a_i$, 其范围为 $(l_i, r_i)$。选择尽量多个区间，使得这些区间两两没有公共点，这些区间称为最大兼容区间。

将所有的区间按照右端点从小到大的顺序进行排序。

最优子结构

用 $S_{ij}$表示在 $a_i$ 结束之后，$a_j$ 结束之前的活动集合，假设 $S_{ij}$ 的最优活动选择中包含区间 $a_k$，那么，我们应该在 $S_{ik}$ 和 $S_{kj}$ 找到最优的活动选择，再加上 $a_k$。得到 $S_{ij}$ 的最优活动选择。

贪心解法步骤

1.将所有的区间按照右端点 $r_i$ 从小到大的顺序进行排列。

2.将排在第一的区间纳入我们的选择。（这是我们的贪心选择）

3.接下来我们只需在剩下的且与已选区间相容的区间中重复操作，直到处理完所有区间。

证明

考虑任何一个非空子问题 $S_k$，令 $a_m$ 是 $S_k$ 中结束最早的活动，设 $A_k$ 是 $S_k$ 的一个最大兼容活动子集（区间之间两两没有公共点）， 假设 $a_m$ 不在 $A_k$ 中，且 $a_j$ 是 $A_k$ 中最早结束的活动。那么，我们可以将 $a_m$ 替换成 $a_j$，因为 $a_m$ 的结束时间不晚于 $a_j$，故 $a_m$ 不会和 $A_k$ 中的其它活动冲突，故替换后的集合依然是一个最大兼容子集。可以证明我们的贪心选择可以得到一个最优的结果。

注意

1. 如果题目给出的是闭区间，我们也这样处理。有区别的地方在于区间是否有公共点的判断。
2. 也可以按照左端点排序，但这时我们需要左端点从大到小排序，且优先选择左端点更大且与已选区间不冲突的区间。这样可以尽可能给左边区间留下更大的空间。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int n;
pair<int, int> A[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> A[i].first >> A[i].second;
    sort(A + 1, A + n + 1, [] (auto a, auto b) {
        return a.second < b.second;
    });
    
    int lst_right = -1, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (A[i].first < lst_right) continue;
        cnt++;
        lst_right = A[i].second;
    }
    cout << cnt << endl;
} 

区间选点问题

区间选点问题(Interval Point Covering Problem)

数轴上有 $n$ 个闭区间 $[l_i, r_i]$。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

最优子结构

假设最优解包含某个点 $p$，那么，我们去掉包含点 $p$ 的区间，在剩余区间的最优解加上点 $p$，便是整个问题的最优解。

贪心解法步骤

1. 将所有区间按照右端点 $r_i$ 排序。
2. 选取排第一个区间的右端点，将其纳入最优解包含的点集中。
3. 接下来，依次处理每个区间，
   • 当前区间的左端点小于等于最后一个选定点，则跳过该区间。
   • 当前区间的左端点大于最后一个选定点，这时我们将该区间的右端点纳入最优解。

证明

如图所示，假设我们另选了一个点 $x$，假设 $x$ 在某个区间 $[l, r]$ 内，所以 $l \le x$，所以 $l \le A$，同时 $A \le r$。所以点 $A$ 一定也在该区间内。反之，若点 $A$ 位于某区间，点 $x$ 不一定在该区间内。综上，我们选择右端点，结果不会比选择其他点更差。

注意

可以看到，本问题的解法和区间调度问题的解法是一样的。最少选点数 = 最大兼容区间。最大兼容区间问题中，选出 $k$ 个互不重合的区间；因为这 $k$ 个区间两两不相交，所以你至少需要 $k$ 个不同的点才能覆盖它们。而贪心算法证明了，$k$ 个点也足够覆盖所有的区间。

参考代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 1000 + 5;
pii A[N];
int n;

bool cmp(const pii &a, const pii &b) {
  return a.second < b.second;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> A[i].first >> A[i].second;
  sort(A + 1, A + n + 1, cmp);
  
  int lst = 0;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (A[i].first > lst) {
      cnt++;
      lst = A[i].second;
    } 
  }
  cout << cnt << endl;
}

区间覆盖问题

区间覆盖问题(Interval Covering Problem)

数轴上有 $n$ 个闭区间 $[a_i, b_i]$，选择尽量少的区间覆盖一条指定线段 $[s,t]$。

最优子结构

贪心解法步骤

1. 将所有区间按照 $a_i$ 从小到大的顺序进行排列。
2. 寻找满足 $a_i \le s$，且 $b_i$ 最大的区间，记该区间对应的 $b_i$ 为 $y_0$。（这是我们的贪心选择）
3. 在后面的区间中，不断寻找满足 $a_i \le y_0$，且 $b_i$ 最大的区间。将该区间的右端点值赋给 $y_0$。直到 $y_0 \ge t$ 结束循环。

参考代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 1000 + 5;
pii A[N];
int n, s, t;

int main() {
  cin >> n >> s >> t;
  for (int i = 1; i <= n; i++) cin >> A[i].first >> A[i].second;  
  sort(A + 1, A + n + 1);
  
  int cnt = 0, i = 0, lst = s;  // [s, lst] 是已经覆盖的区间
  while (lst < t) {  
    int tmp = 0;  
    while (i + 1 <= n && A[i + 1].first <= lst) tmp = max(tmp, A[++i].second);
    if (tmp == 0) { cout << "-1";  return 0;  }
    lst = tmp;
    cnt++;
  } 
  cout << cnt << endl;  
}

证明

相关题目

例1.

例2.

例3.